package code.oldCode.feishuSpecializedTraining.monotone_stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 26029
 * @date 2025/4/6
 * @description
 */
public class MyMS2 {
    // 42. 接雨水
    public int trap(int[] height) {
        // dp做法，对于每一个位置，找出其左面最高的墙高和右面最高的墙高，他俩取最小值就是这个位置的雨水量
        int len = height.length;
        int[] leftMax = new int[len], rightMax = new int[len];
        int leftNowMax = 0, rightNowMax = 0;
        for (int i = 0; i < len; i++) {
            leftMax[i] = leftNowMax;
            leftNowMax = Math.max(leftNowMax, height[i]);
            int j = len - 1 - i;
            rightMax[j] = rightNowMax;
            rightNowMax = Math.max(rightNowMax, height[j]);
        }

        int ans = 0;
        for (int i = 0; i < len; i++) {
            int minLR = Math.min(leftMax[i], rightMax[i]);
            if (minLR > height[i]) {
                ans += minLR - height[i];
            }
        }

        return ans;
    }

    public int trap_ms(int[] height) {
        // 单调栈做法,不好理解
        int ans = 0;
        Deque<Integer> ms = new LinkedList<>();
        int len = height.length;
        for (int i = 0; i < len; ++i) {
            while (!ms.isEmpty() && height[i] > height[ms.peek()]) {
                // 确保ms中有两个，组成下壁和左壁
                int flat = ms.pop();
                if (ms.isEmpty())
                    break;
                int left = ms.peek();
                // 计算这一部分的答案
                int wid = i - left - 1;
                int hei = Math.min(height[i], height[left]) - height[flat];
                ans += wid * hei;
            }
            ms.push(i);
        }
        return ans;
    }

    // 84. 柱状图中最大的矩形
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int ans = 0;
        Deque<Integer> ms = new LinkedList<>();
        // 遍历两次，找到left[]和right[]，left[i]right[i]表示当前位置能向左向右扩展的最远位置(的下一个位置)
        // 也就是，left[]遍历找到左面第一个比他小的，right[]找到右面第一个比他小的
        // 单调栈找不到最后一个比他大(小)的，只能找到第一个比他大(小)的!!!
        int[] left = new int[len], right = new int[len];
        // so，递增栈，push的越来越大，pop的越来越小
        for (int i = 0; i < len; i++) {
            while (!ms.isEmpty() && heights[i] <= heights[ms.peek()]) {
                ms.pop();
            }
            // 若当前为空，说明左面都比它大，则可以扩展到最左面，若不为空，则有比他大的
            if (!ms.isEmpty()) {
                left[i] = ms.peek();
            } else {
                left[i] = -1;
            }
            ms.push(i);
        }
        ms.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (!ms.isEmpty() && heights[i] <= heights[ms.peek()]) {
                ms.pop();
            }
            if (!ms.isEmpty()) {
                right[i] = ms.peek();
            } else {
                right[i] = len;
            }
            ms.push(i);
        }
        for (int i = 0; i < len; i++) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }

    public static void main(String[] args) {
        MyMS2 m = new MyMS2();
        System.out.println(m.largestRectangleArea(new int[]{3,6,5,7,4,8,1,0}));
    }
}
